Many systems, including embedded systems, have real-time timeliness constraints on their processing. Such systems often interact with the real world and/or users and have specific constraints on when they must respond to events, produce results, etc. Some examples of such systems include safety-critical systems such as anti-lock brakes, control systems such as flight control systems, multimedia systems such as video or audio players, and so forth. Systems intended to address such real-time situations must be carefully designed to ensure the timing requirements of the applications they are built to execute.
The CPU scheduler is a core operating system component responsible for managing the execution scheduling of different programs. The CPU scheduler is responsible for determining which program to run at any given time. Where programs have implicit or explicit timeliness constraints or deadlines, the CPU scheduler is primarily responsible for ensuring that the applications execute in time to satisfy the timeliness constraints or deadlines. Many different operating systems and CPU schedulers have been developed to address various sorts of timing requirements.
One type of scheduler that is frequently used in legacy systems (e.g., military and aerospace systems) is based on static schedules. Static schedules are very basic table-driven schedules that include an ordered list of tasks along with a set of times at which those tasks should occur. Upon completion of all of the tasks in the list, the list typically repeats with a fixed frequency, or period. Static schedules are common in legacy systems due in part to their extreme simplicity. However, static schedules are limited in their use because each static schedule is essentially hand-designed to ensure that all work can be completed in the time available. This is feasible only for small task sets.
In contrast to static schedules, other schedulers use dynamic schedules. One type of dynamic schedule is a dynamic priority-based schedule. Priority scheduling (e.g., rate monotonic (RM)) assigns a static priority to each concurrently executing task. Tasks are executed according to their priority, with the highest priority task that is currently executable always selected for execution. A limitation of static priority-based schedules is that in general only a relatively low fraction of the CPU utilization may be guaranteed. Another type of dynamic schedule is a dynamic deadline-based schedule. Deadline scheduling assigns a set of deadlines to each task. In one deadline-based scheduling algorithm known as earliest deadline first (EDF), the system always runs the task with the earliest deadline. An advantage of EDF is that 100% of the CPU utilization may be guaranteed. However, EDF is less frequently used due to concerns about its overhead. Recent research indicates that deadline based schemes are effective in supporting a broad range of types of processes ranging from best-effort to hard real-time.
An advantage of RM and EDF dynamic scheduling schemes is that they allow the concurrent execution of different applications with different timeliness requirements with less hand-integration than a static schedule. In this way, each application can be admitted to the system based on knowledge of the resource availability, without detailed knowledge of the other applications. A potential disadvantage of RM and EDF dynamic scheduling is that they are incapable of supporting legacy processes designed to operate in isolation with static schedulers. This prevents the migration of legacy applications and systems to modern multi-programmed processing platforms. Since legacy applications that use static scheduling are common in aerospace, automotive, and other industries, there are many legacy applications that currently cannot be integrated into modern multi-programmed processing platforms that use dynamic scheduling.